//
// Depth-First Iterative Deepening
//
#ifndef __SEARCH_DFID_H__
#define __SEARCH_DFID_H__

#pragma once

#include "Search.h"
#include <vector>

using namespace std;

class SearchDFID : public Search
{
public:
	// Input: start state
	// Output: cost of solution and the solution path.
	// Returns: true if solution found, otherwise false.
	virtual bool run(State &s, Solution &solution)
	{
		// Iterate on depth threshold until solution is found.
		m_nodesExpanded = 0; // reset nodes expanded.
		int  depth  = 0;
		bool solved = false;
		while (!solved) {
			solved = DFS(s, depth, solution);
			depth++;
		}

		// reverse solution.m_actions
		/*
		vector<int>::size_type sza = solution.size();
		for (int i=0; i<int(sza/2); i++)
		{
			Action temp;
			temp = solution.m_actions[sza-1-i];
			solution.m_actions[sza-1-i] = solution.m_actions[i];
			solution.m_actions[i] = temp;
		}

		// reverse solution.m_stateids
		Solution 
		for (int j=0; j<int(szb/2); j++)
		{
			long temp;
			temp = solution.m_stateids[szb-1-j];
			solution.m_stateids[szb-1-j] = solution.m_stateids[j];
			solution.m_stateids[j] = temp;
		}
		*/
		return solved;
	}
	
	virtual bool run(State& s, Cost& cost, Solution& solution)
	{
		return run(s, solution);
	}
	
	// Get number of nodes expanded.
	NI getNodesExpanded()
	{
		return m_nodesExpanded;
	}

private:	
	NI m_nodesExpanded;
	// Depth-bounded Depth-First Search
	bool DFS(State &s, int depth, Solution &solution)
	{
		// If goal is found then return success, else if depth limit
		// is reached return failure.
		if (s.isGoal()) {
			return true;
		}
		else if (depth <= 0) {
			return false;
		}

		// Iterate through the successors recursively invoking DFS.
		vector<GWAction> actions;
		s.getActions(actions);
		m_nodesExpanded++;
		bool solved = false;
		for (int i=0; i < (int) actions.size() ; ++i) {
			s.make(actions.at(i));
			solved = DFS(s, depth-1, solution);
			s.retract(actions.at(i));
			if (solved) {
				solution.push_back(actions.at(i));
				break;
			}
		}

		// Return the status of the search (solution found or not).
		return solved;
	}
};

#endif // __SEARCH_DFID_H__
